#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <time.h>

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void PrintArray(int* a, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

int GetMiddle(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else if (a[mid] > a[right])
			return mid;
		else
			return right;
	}
}


//快速排序
void QuickSort1(int* a, int left, int right)
{
	//当key==end的时候再次递归，left会大于right
	if (left >= right)
		return;
	int begin = left, end = right;
	//随机选key
//int randi = left + (rand() % (right - left));
//Swap(&a[randi], &a[left]);

	//三数取中-尽量分开两个等长的区间
	int midi = GetMiddle(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		//先从右边找小
		while (left < right && a[right] >= a[keyi])
			--right;

		//再从左边找大
		while (left < right && a[left] <= a[keyi])
			++left;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;
	QuickSort1(a, begin, keyi - 1);//交点是left也是right
	QuickSort1(a, keyi + 1, end);
}

int PartSort1(int* a, int left, int right)
{

	//三数取中-尽量分开两个等长的区间
	int midi = GetMiddle(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	while (left < right)
	{
		//先从右边找小
		while (left < right && a[right] >= a[keyi])
			--right;

		//再从左边找大
		while (left < right && a[left] <= a[keyi])
			++left;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;
	return keyi;
}


//挖坑法
void QuickSort2(int* a, int left, int right)
{
	//当key==end的时候再次递归，left会大于right
	if (left >= right)
		return;
	//随机选key
//int randi = left + (rand() % (right - left));
//Swap(&a[randi], &a[left]);

	//三数取中-尽量分开两个等长的区间
	int midi = GetMiddle(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int begin = left, end = right;
	int hole = left;
	while (left < right)
	{
		//右边先找小，左边在找大
		while (left < right && a[right] >= key)
			right--;
		//这里不用加判断，没有找到的话就是原来的坑位
		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
			left++;

		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;

	QuickSort2(a, begin, hole - 1);//交点是left也是right
	QuickSort2(a, hole + 1, end);
}

int PartSort2(int* a, int left, int right)
{
	//三数取中-尽量分开两个等长的区间
	int midi = GetMiddle(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边先找小，左边在找大
		while (left < right && a[right] >= key)
			right--;
		//这里不用加判断，没有找到的话就是原来的坑位
		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
			left++;

		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

int PartSort3(int* a, int left, int right)
{
	//三数取中-尽量分开两个等长的区间
	int midi = GetMiddle(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = a[left];
	int prev = left, cur = left + 1;
	//prev是找小的前面一个位置
	//prev要么紧跟着cur，要么中间隔着一段比key大的值,prev则指向大数
	while (cur <= right)
	{
		if (a[cur] >= key)
		{
			++cur;
		}
		else
		{
			++prev;//++则指向大数，在对调
			if (prev != cur)
				Swap(&a[prev], &a[cur]);
			++cur;
		}
		//if (a[cur] < key)
		//{
		//	++prev;
		//	if (prev != cur)
		//		Swap(&a[prev], &a[cur]);
		//}
		//++cur;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}